package com.sgffsg.learn.javalib.algorithm;

import java.util.Arrays;

/**
 * 堆排序解题
 */
class Solution {

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] nums = new int[]{3,2,1,5,6,4};
        solution.findKthLargest(nums, 2);
    }
    public int findKthLargest(int[] nums, int k) {

        int length = nums.length;
        int startIndex = (length - 1) / 2;
        for (int i = startIndex; i >= 0; i--) {
            System.out.println("i = " + i +",nums = "+ Arrays.toString(nums));
            heapify(nums, k, length, i);
        }
        System.out.println("开始排序---- ");
//        for (int i = length - 1; i > 0; i--) {
//            System.out.println("i = " + i +",nums = "+ Arrays.toString(nums));
//            swap(nums, i, 0);
//            heapify(nums, k, i, 0);
//        }

        for (int i = length - 1; i >= length - k; i--) {
            System.out.println("i = " + i +",nums = "+ Arrays.toString(nums));
            swap(nums, i, 0);
            heapify(nums, k, i, 0);
        }
        System.out.println("结果 nums = "+ Arrays.toString(nums));
        return nums[length - k];
    }

    private void heapify(int[] nums, int k, int lengtn,int index) {
        int leftChildIndex = index * 2 + 1;
        int rightChildIndex = index * 2 + 2;
        int largeIndex = index;
        if(leftChildIndex < lengtn && nums[leftChildIndex] > nums[largeIndex]){
//            System.out.println("leftChildIndex = "+ leftChildIndex+", index = "+ index);
            largeIndex = leftChildIndex;
        }
        if(rightChildIndex < lengtn && nums[rightChildIndex] > nums[largeIndex]) {
//            System.out.println("rightChildIndex = "+ rightChildIndex+", index = "+ index);
            largeIndex = rightChildIndex;
        }
        System.out.println("lengtn = "+ lengtn+", index = "+ index+", largeIndex = "+ largeIndex);
        if (largeIndex != index) {
            swap(nums, largeIndex, index);
            heapify(nums, k, lengtn, largeIndex);
        }



    }

    private void swap(int[] nums, int l, int r) {
        int temp = nums[l];
        nums[l] = nums[r];
        nums[r] = temp;
    }
}